home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 101-125 / disk_105 / bison / lalr.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  14KB  |  750 lines
  1. /* Compute look-ahead criteria for bison,
  2.    copyright (C) 1984 Bob Corbett and Richard Stallman
  3.  
  4.    Permission is granted to anyone to make or distribute verbatim copies of this program
  5.    provided that the copyright notice and this permission notice are preserved;
  6.    and provided that the recipient is not asked to waive or limit his right to
  7.    redistribute copies as permitted by this permission notice;
  8.    and provided that anyone possessing an executable copy
  9.    is granted access to copy the source code, in machine-readable form,
  10.    in some reasonable manner.
  11.  
  12.    Permission is granted to distribute derived works or enhanced versions of
  13.    this program under the above conditions with the additional condition
  14.    that the entire derivative or enhanced work
  15.    must be covered by a permission notice identical to this one.
  16.  
  17.    Anything distributed as part of a package containing portions derived
  18.    from this program, which cannot in current practice perform its function usefully
  19.    in the absense of what was derived directly from this program,
  20.    is to be considered as forming, together with the latter,
  21.    a single work derived from this program,
  22.    which must be entirely covered by a permission notice identical to this one
  23.    in order for distribution of the package to be permitted.
  24.  
  25.  In other words, you are welcome to use, share and improve this program.
  26.  You are forbidden to forbid anyone else to use, share and improve
  27.  what you give them.   Help stamp out software-hoarding!  */
  28.  
  29. /* Compute how to make the finite state machine deterministic;
  30.  find which rules need lookahead in each state, and which lookahead tokens they accept.
  31.  
  32. lalr(), the entry point, builds these data structures:
  33.  
  34. goto_map, from_state and to_state 
  35.  record each shift transition which accepts a variable (a nonterminal).
  36. ngotos is the number of such transitions.
  37. from_state[t] is the state number which a transition leads from
  38. and to_state[t] is the state number it leads to.
  39. All the transitions that accept a particular variable are grouped together and
  40. goto_map[i - ntokens] is the index in from_state and to_state of the first of them.
  41.  
  42. consistent[s] is nonzero if no lookahead is needed to decide what to do in state s.
  43.  
  44. LAruleno is a vector which records the rules that need lookahead in various states.
  45. The elements of LAruleno that apply to state s are those from
  46.  lookaheads[s] through lookaheads[s+1]-1.
  47. Each element of LAruleno is a rule number.
  48.  
  49. If lr is the length of LAruleno, then a number from 0 to lr-1 
  50. can specify both a rule and a state where the rule might be applied.
  51.  
  52. LA is a lr by ntokens matrix of bits.
  53. LA[l, i] is 1 if the rule LAruleno[l] is applicable in the appropriate state
  54.  when the next token is symbol i.
  55. If LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict.
  56. */
  57.  
  58. #include <stdio.h>
  59. #include "machine.h"
  60. #include "types.h"
  61. #include "state.h"
  62. #include "new.h"
  63. #include "gram.h"
  64.  
  65.  
  66. extern short **derives;
  67. extern char *nullable;
  68.  
  69.  
  70. int tokensetsize;
  71. short *lookaheads;
  72. short *LAruleno;
  73. unsigned *LA;
  74. short *accessing_symbol;
  75. char *consistent;
  76. core **state_table;
  77. shifts **shift_table;
  78. reductions **reduction_table;
  79. short *goto_map;
  80. short *from_state;
  81. short *to_state;
  82.  
  83. short **transpose();
  84.  
  85.  
  86. static int infinity;
  87. static int maxrhs;
  88. static int ngotos;
  89. static unsigned *F;
  90. static short **includes;
  91. static shorts **lookback;
  92. static short **R;
  93. static short *INDEX;
  94. static short *VERTICES;
  95. static int top;
  96.  
  97.  
  98.  
  99. lalr()
  100. {
  101.   tokensetsize = WORDSIZE(ntokens);
  102.  
  103.   set_state_table();
  104.   set_accessing_symbol();
  105.   set_shift_table();
  106.   set_reduction_table();
  107.   set_maxrhs();
  108.   initialize_LA();
  109.   set_goto_map();
  110.   initialize_F();
  111.   build_relations();
  112.   compute_FOLLOWS();
  113.   compute_lookaheads();
  114. }
  115.  
  116.  
  117.  
  118. set_state_table()
  119. {
  120.   register core *sp;
  121.  
  122.   state_table = NEW2(nstates, core *);
  123.  
  124.   for (sp = first_state; sp; sp = sp->next)
  125.     state_table[sp->number] = sp;
  126. }
  127.  
  128.  
  129.  
  130. set_accessing_symbol()
  131. {
  132.   register core *sp;
  133.  
  134.   accessing_symbol = NEW2(nstates, short);
  135.  
  136.   for (sp = first_state; sp; sp = sp->next)
  137.     accessing_symbol[sp->number] = sp->accessing_symbol;
  138. }
  139.  
  140.  
  141.  
  142. set_shift_table()
  143. {
  144.   register shifts *sp;
  145.  
  146.   shift_table = NEW2(nstates, shifts *);
  147.  
  148.   for (sp = first_shift; sp; sp = sp->next)
  149.     shift_table[sp->number] = sp;
  150. }
  151.  
  152.  
  153.  
  154. set_reduction_table()
  155. {
  156.   register reductions *rp;
  157.  
  158.   reduction_table = NEW2(nstates, reductions *);
  159.  
  160.   for (rp = first_reduction; rp; rp = rp->next)
  161.     reduction_table[rp->number] = rp;
  162. }
  163.  
  164.  
  165.  
  166. set_maxrhs()
  167. {
  168.   register short *itemp;
  169.   register int length;
  170.   register int maxlength;
  171.  
  172.   length = 0;
  173.   maxlength = 0;
  174.   for (itemp = ritem; *itemp; itemp++)
  175.     {
  176.       if (*itemp > 0)
  177.     {
  178.       length++;
  179.     }
  180.       else
  181.     {
  182.       if (length > maxlength) maxlength = length;
  183.       length = 0;
  184.     }
  185.     }
  186.  
  187.   maxrhs = maxlength;
  188. }
  189.  
  190.  
  191.  
  192. initialize_LA()
  193. {
  194.   register int i;
  195.   register int j;
  196.   register int count;
  197.   register reductions *rp;
  198.   register shifts *sp;
  199.   register short *np;
  200.  
  201.   consistent = NEW2(nstates, char);
  202.   lookaheads = NEW2(nstates + 1, short);
  203.  
  204.   count = 0;
  205.   for (i = 0; i < nstates; i++)
  206.     {
  207.       lookaheads[i] = count;
  208.  
  209.       rp = reduction_table[i];
  210.       sp = shift_table[i];
  211.       if (rp && (rp->nreds > 1
  212.           || (sp && ! ISVAR(accessing_symbol[sp->shifts[0]]))))
  213.     count += rp->nreds;
  214.       else
  215.     consistent[i] = 1;
  216.       if (sp)
  217.         for (j = 0; j < sp->nshifts; j++)
  218.       {
  219.         if (accessing_symbol[sp->shifts[j]] == error_token_number)
  220.           {
  221.             consistent[i] = 0;
  222.             break;
  223.           }
  224.       }
  225.     }
  226.  
  227.   lookaheads[nstates] = count;
  228.  
  229.   LA = NEW2(count * tokensetsize, unsigned);
  230.   LAruleno = NEW2(count, short);
  231.   lookback = NEW2(count, shorts *);
  232.  
  233.   np = LAruleno;
  234.   for (i = 0; i < nstates; i++)
  235.     {
  236.       if (!consistent[i])
  237.     {
  238.       rp = reduction_table[i];
  239.       if(rp)
  240.         {
  241.           for (j = 0; j < rp->nreds; j++)
  242.         *np++ = rp->rules[j];
  243.         }
  244.     }
  245.     }
  246. }
  247.  
  248.  
  249.  
  250. set_goto_map()
  251. {
  252.   register shifts *sp;
  253.   register int i;
  254.   register int symbol;
  255.   register int k;
  256.   register short *temp_map;
  257.   register int state2;
  258.   register int state1;
  259.  
  260.   goto_map = NEW2(nvars + 1, short) - ntokens;
  261.   temp_map = NEW2(nvars + 1, short) - ntokens;
  262.  
  263.   ngotos = 0;
  264.   for (sp = first_shift; sp; sp = sp->next)
  265.     {
  266.       for (i = sp->nshifts - 1; i >= 0; i--)
  267.     {
  268.       symbol = accessing_symbol[sp->shifts[i]];
  269.  
  270.       if (ISTOKEN(symbol)) break;
  271.  
  272.       if (ngotos == MAXSHORT)
  273.         toomany("gotos");
  274.  
  275.       ngotos++;
  276.       goto_map[symbol]++;
  277.         }
  278.     }
  279.  
  280.   k = 0;
  281.   for (i = ntokens; i < nsyms; i++)
  282.     {
  283.       temp_map[i] = k;
  284.       k += goto_map[i];
  285.     }
  286.  
  287.   for (i = ntokens; i < nsyms; i++)
  288.     goto_map[i] = temp_map[i];
  289.  
  290.   goto_map[nsyms] = ngotos;
  291.   temp_map[nsyms] = ngotos;
  292.  
  293.   from_state = NEW2(ngotos, short);
  294.   to_state = NEW2(ngotos, short);
  295.  
  296.   for (sp = first_shift; sp; sp = sp->next)
  297.     {
  298.       state1 = sp->number;
  299.       for (i = sp->nshifts - 1; i >= 0; i--)
  300.     {
  301.       state2 = sp->shifts[i];
  302.       symbol = accessing_symbol[state2];
  303.  
  304.       if (ISTOKEN(symbol)) break;
  305.  
  306.       k = temp_map[symbol]++;
  307.       from_state[k] = state1;
  308.       to_state[k] = state2;
  309.     }
  310.     }
  311.  
  312.   FREE(temp_map + ntokens);
  313. }
  314.  
  315.  
  316.  
  317. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  318.  
  319. int
  320. map_goto(state, symbol)
  321. int state;
  322. int symbol;
  323. {
  324.   register int high;
  325.   register int low;
  326.   register int middle;
  327.   register int s;
  328.  
  329.   low = goto_map[symbol];
  330.   high = goto_map[symbol + 1];
  331.  
  332.   while (low <= high)
  333.     {
  334.       middle = (low + high) / 2;
  335.       s = from_state[middle];
  336.       if (s == state)
  337.     return (middle);
  338.       else if (s < state)
  339.     low = middle + 1;
  340.       else
  341.     high = middle - 1;
  342.     }
  343.  
  344.   berror("map_goto");
  345.  
  346. /* NOTREACHED */
  347. }
  348.  
  349.  
  350.  
  351. initialize_F()
  352. {
  353.   register int i;
  354.   register int j;
  355.   register int k;
  356.   register shifts *sp;
  357.   register short *edge;
  358.   register unsigned *rowp;
  359.   register short *rp;
  360.   short **reads;
  361.   register int nedges;
  362.   register int stateno;
  363.   register int symbol;
  364.   int nwords;
  365.  
  366.   nwords = ngotos * tokensetsize;
  367.   F = NEW2(nwords, unsigned);
  368.  
  369.   reads = NEW2(ngotos, short *);
  370.   edge = NEW2(ngotos + 1, short);
  371.   nedges = 0;
  372.  
  373.   rowp = F;
  374.   for (i = 0; i < ngotos; i++)
  375.     {
  376.       stateno = to_state[i];
  377.       sp = shift_table[stateno];
  378.  
  379.       if (sp)
  380.     {
  381.       k = sp->nshifts;
  382.  
  383.       for (j = 0; j < k; j++)
  384.         {
  385.           symbol = accessing_symbol[sp->shifts[j]];
  386.           if (ISVAR(symbol))
  387.         break;
  388.           SETBIT(rowp, symbol);
  389.         }
  390.  
  391.       for (; j < k; j++)
  392.         {
  393.           symbol = accessing_symbol[sp->shifts[j]];
  394.           if (nullable[symbol])
  395.         edge[nedges++] = map_goto(stateno, symbol);
  396.         }
  397.     
  398.       if (nedges)
  399.         {
  400.           reads[i] = rp = NEW2(nedges + 1, short);
  401.  
  402.           for (j = 0; j < nedges; j++)
  403.         rp[j] = edge[j];
  404.  
  405.           rp[nedges] = -1;
  406.           nedges = 0;
  407.         }
  408.     }
  409.  
  410.       rowp += tokensetsize;
  411.     }
  412.  
  413.   digraph(reads);
  414.  
  415.   for (i = 0; i < ngotos; i++)
  416.     {
  417.       if (reads[i])
  418.     FREE(reads[i]);
  419.     }
  420.  
  421.   FREE(reads);
  422.   FREE(edge);
  423. }
  424.  
  425.  
  426.  
  427. build_relations()
  428. {
  429.   register int i;
  430.   register int j;
  431.   register int k;
  432.   register short *rulep;
  433.   register short *rp;
  434.   register shifts *sp;
  435.   register int length;
  436.   register int nedges;
  437.   register int done;
  438.   int state1;
  439.   int stateno;
  440.   int symbol1;
  441.   int symbol2;
  442.   register short *shortp;
  443.   short *edge;
  444.   short *states;
  445.   short **new_includes;
  446.  
  447.   includes = NEW2(ngotos, short *);
  448.   edge = NEW2(ngotos + 1, short);
  449.   states = NEW2(maxrhs + 1, short);
  450.  
  451.   for (i = 0; i < ngotos; i++)
  452.     {
  453.       nedges = 0;
  454.       state1 = from_state[i];
  455.       symbol1 = accessing_symbol[to_state[i]];
  456.  
  457.       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
  458.     {
  459.       length = 1;
  460.       states[0] = state1;
  461.       stateno = state1;
  462.  
  463.       for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
  464.         {
  465.           symbol2 = *rp;
  466.           sp = shift_table[stateno];
  467.           k = sp->nshifts;
  468.  
  469.           for (j = 0; j < k; j++)
  470.         {
  471.           stateno = sp->shifts[j];
  472.           if (accessing_symbol[stateno] == symbol2) break;
  473.         }
  474.  
  475.           states[length++] = stateno;
  476.         }
  477.  
  478.       if (!consistent[stateno])
  479.         add_lookback_edge(stateno, *rulep, i);
  480.  
  481.       length--;
  482.       done = (length == 0);
  483.       while (!done)
  484.         {
  485.           done = 1;
  486.           rp--;
  487.           if (ISVAR(*rp))
  488.         {
  489.           stateno = states[--length];
  490.           edge[nedges++] = map_goto(stateno, *rp);
  491.           if (nullable[*rp]) done = 0;
  492.         }
  493.         }
  494.     }
  495.  
  496.       if (nedges)
  497.     {
  498.       includes[i] = shortp = NEW2(nedges + 1, short);
  499.       for (j = 0; j < nedges; j++)
  500.         shortp[j] = edge[j];
  501.       shortp[nedges] = -1;
  502.     }
  503.     }
  504.  
  505.   new_includes = transpose(includes, ngotos);
  506.  
  507.   for (i = 0; i < ngotos; i++)
  508.     FREE(includes[i]);
  509.  
  510.   FREE(includes);
  511.  
  512.   includes = new_includes;
  513.  
  514.   FREE(edge);
  515.   FREE(states);
  516. }
  517.  
  518.  
  519.  
  520. add_lookback_edge(stateno, ruleno, gotono)
  521. int stateno;
  522. int ruleno;
  523. int gotono;
  524. {
  525.   register int i;
  526.   register int k;
  527.   register int found;
  528.   register shorts *sp;
  529.  
  530.   i = lookaheads[stateno];
  531.   k = lookaheads[stateno + 1];
  532.   found = 0;
  533.   while (!found && i < k)
  534.     {
  535.       if (LAruleno[i] == ruleno)
  536.     found = 1;
  537.       else
  538.     i++;
  539.     }
  540.  
  541.   if (found == 0)
  542.     berror("add_lookback_edge");
  543.  
  544.   sp = NEW(shorts);
  545.   sp->next = lookback[i];
  546.   sp->value = gotono;
  547.   lookback[i] = sp;
  548. }
  549.  
  550.  
  551.  
  552. short **
  553. transpose(R, n)
  554. short **R;
  555. int n;
  556. {
  557.   register short **new_R;
  558.   register short **temp_R;
  559.   register short *nedges;
  560.   register short *sp;
  561.   register int i;
  562.   register int k;
  563.  
  564.   nedges = NEW2(n, short);
  565.  
  566.   for (i = 0; i < n; i++)
  567.     {
  568.       sp = R[i];
  569.       if (sp)
  570.     {
  571.       while (*sp >= 0)
  572.         nedges[*sp++]++;
  573.     }
  574.     }
  575.  
  576.   new_R = NEW2(n, short *);
  577.   temp_R = NEW2(n, short *);
  578.  
  579.   for (i = 0; i < n; i++)
  580.     {
  581.       k = nedges[i];
  582.       if (k > 0)
  583.     {
  584.       sp = NEW2(k + 1, short);
  585.       new_R[i] = sp;
  586.       temp_R[i] = sp;
  587.       sp[k] = -1;
  588.     }
  589.     }
  590.  
  591.   FREE(nedges);
  592.  
  593.   for (i = 0; i < n; i++)
  594.     {
  595.       sp = R[i];
  596.       if (sp)
  597.     {
  598.       while (*sp >= 0)
  599.         *temp_R[*sp++]++ = i;
  600.     }
  601.     }
  602.  
  603.   FREE(temp_R);
  604.  
  605.   return (new_R);
  606. }
  607.  
  608.  
  609.  
  610. compute_FOLLOWS()
  611. {
  612.   register int i;
  613.  
  614.   digraph(includes);
  615.  
  616.   for (i = 0; i < ngotos; i++)
  617.     {
  618.       if (includes[i]) FREE(includes[i]);
  619.     }
  620.  
  621.   FREE(includes);
  622. }
  623.  
  624.  
  625.  
  626. compute_lookaheads()
  627. {
  628.   register int i;
  629.   register int n;
  630.   register unsigned *fp1;
  631.   register unsigned *fp2;
  632.   register unsigned *fp3;
  633.   register shorts *sp;
  634.   shorts *sptrail;
  635.   unsigned *rowp;
  636.  
  637.   rowp = LA;
  638.   n = lookaheads[nstates];
  639.   for (i = 0; i < n; i++)
  640.     {
  641.       fp3 = rowp + tokensetsize;
  642.       for (sp = lookback[i]; sp; sp = sp->next)
  643.     {
  644.       fp1 = rowp;
  645.       fp2 = F + tokensetsize * sp->value;
  646.       while (fp1 < fp3)
  647.         *fp1++ |= *fp2++;
  648.     }
  649.  
  650.       rowp = fp3;
  651.     }
  652.  
  653.   for (i = 0; i < n; i++)
  654.     {
  655.       for (sp = lookback[i]; sp;) {
  656.     sptrail = sp;
  657.     sp = sp->next;
  658.     FREE(sptrail);
  659.       }
  660.     }
  661.  
  662.   FREE(lookback);
  663.   FREE(F);
  664. }
  665.  
  666.  
  667.  
  668. digraph(relation)
  669. short **relation;
  670. {
  671.   register int i;
  672.  
  673.   infinity = ngotos + 2;
  674.   INDEX = NEW2(ngotos + 1, short);
  675.   VERTICES = NEW2(ngotos + 1, short);
  676.   top = 0;
  677.  
  678.   R = relation;
  679.  
  680.   for (i = 0; i < ngotos; i++)
  681.     INDEX[i] = 0;
  682.  
  683.   for (i = 0; i < ngotos; i++)
  684.     {
  685.       if (INDEX[i] == 0 && R[i])
  686.     traverse(i);
  687.     }
  688.  
  689.   FREE(INDEX);
  690.   FREE(VERTICES);
  691. }
  692.  
  693.  
  694.  
  695. traverse(i)
  696. register int i;
  697. {
  698.   register unsigned *fp1;
  699.   register unsigned *fp2;
  700.   register unsigned *fp3;
  701.   register int j;
  702.   register short *rp;
  703.  
  704.   int height;
  705.   unsigned *base;
  706.  
  707.   VERTICES[++top] = i;
  708.   INDEX[i] = height = top;
  709.  
  710.   base = F + i * tokensetsize;
  711.   fp3 = base + tokensetsize;
  712.  
  713.   rp = R[i];
  714.   if (rp)
  715.     {
  716.       while ((j = *rp++) >= 0)
  717.     {
  718.       if (INDEX[j] == 0)
  719.         traverse(j);
  720.  
  721.       if (INDEX[i] > INDEX[j])
  722.         INDEX[i] = INDEX[j];
  723.  
  724.       fp1 = base;
  725.       fp2 = F + j * tokensetsize;
  726.  
  727.       while (fp1 < fp3)
  728.         *fp1++ |= *fp2++;
  729.     }
  730.     }
  731.  
  732.   if (INDEX[i] == height)
  733.     {
  734.       for (;;)
  735.     {
  736.       j = VERTICES[top--];
  737.       INDEX[j] = infinity;
  738.  
  739.       if (i == j)
  740.         break;
  741.  
  742.       fp1 = base;
  743.       fp2 = F + j * tokensetsize;
  744.  
  745.       while (fp1 < fp3)
  746.         *fp2++ = *fp1++;
  747.     }
  748.     }
  749. }
  750.